package interview.huawei.tjt.training.dongtaiguihua;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
 *
 * 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 * 1,5,11,5
 *
 * 示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
 *1,2,3,5
 *
 * 提示：
 *
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 *
 * 转化成01背包问题来求解
 * target值为数组总和的一半，将target的值视为背包的总空间，然后数组元素为各个位置的重量和价值，求出最后的最大价值之后将最大价值和
 * target进行比较，如果等于target，则表示能分割成两个元素和相等的子集
 */
// 一维数组版本
public class CanPartition_2 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String[] strings = scanner.nextLine().split(",");
            int[] nums = new int[strings.length];
            int sum = 0;
            for (int i = 0; i < strings.length; i ++) {
                if (!strings[i].equals("")) {
                    nums[i] = Integer.parseInt(strings[i]);
                    sum += Integer.parseInt(strings[i]);
                }
            }
            if (sum % 2 != 0) {
                System.out.println("false");
            } else {
                int target = sum / 2;
                int[] dp = new int[target + 1];
                for (int i = 0; i < nums.length; i ++) {
                    for (int j = target; j >= nums[i]; j --) {
                        dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                    }
                }
                if (dp[target] == target) {
                    System.out.println("true");
                } else {
                    System.out.println("false");
                }
            }
        }
    }

}
